#include "qe_log.h"
#include "qe_list.h"
#include "qe_hash.h"
#include "qe_array.h"
#include "qe_graph.h"
#include "qe_assert.h"
#include "qe_string.h"
#include "qe_memory.h"



QELOG_DOMAIN(QELOG_DOMAIN_GRAPH);



typedef struct
{
    qe_uint num_edges;
    qe_hashtab *vertices;
    qe_hashtab *adjacency_list;
    qe_val_str v_str_func;
} qe_graph_real;

static qe_str direct_str(qe_const_ptr v)
{
    static char string[16] = {'\0'};
    qe_sprintf("%p", v);
    return (qe_str)string;
}

static qe_array *get_adjacency(qe_graph_real *g, qe_const_ptr v)
{
    return (qe_array *)qe_hashtab_lookup(g->adjacency_list, v);
}

static qe_bool is_in_adjacency(qe_graph_real *g, qe_const_ptr v, qe_const_ptr w)
{
    int i;
    qe_const_ptr p;

    qe_array *adjs = (qe_array *)qe_hashtab_lookup(g->adjacency_list, v);
    if (!adjs) {
        qe_error("v:%s no adjs", g->v_str_func(v));
        return qe_false;
    }

    for (i=0; i<adjs->len; i++) {
        p = qe_array_index(adjs, qe_const_ptr, i);
        if (p == w) {
            return qe_true;
        }
    }

    return qe_false;
}

static qe_ret adjacency_add(qe_graph_real *g, qe_const_ptr v, qe_const_ptr w)
{
    qe_array *adjs = (qe_array *)qe_hashtab_lookup(g->adjacency_list, v);
    qe_array_append(adjs, &w, 1);
    qe_debug("v:%p add adj:%p", v, w);
    return qe_ok;
}

static void adjacency_remove(qe_graph_real *g, qe_const_ptr v, qe_const_ptr w)
{
    int i;
    qe_bool find = qe_false;
    qe_const_ptr n;

    qe_array *adjs = (qe_array *)qe_hashtab_lookup(g->adjacency_list, v);

    for (i=0; i<adjs->len; i++) {
        n = qe_array_index(adjs, qe_const_ptr, i);
        if (n == w) {
            find = qe_true;
            break;
        }
    }

    if (find) {
        qe_array_remove_index(adjs, i);
        qe_debug("v:%p remove adj:%p w:%p", v, adjs, w);
    }
}

static qe_ptr find_vertex(qe_graph_real *g, qe_const_ptr v)
{
    return qe_hashtab_lookup(g->vertices, v);
}

static qe_ret add_vertex(qe_graph_real *g, qe_const_ptr v)
{
    qe_array *adjs;

    /* add to vertex hash */
    qe_hashtab_insert(g->vertices, (qe_ptr)v, (qe_ptr)v);
    qe_debug("add v:%p", v);

    adjs = qe_array_new(sizeof(qe_const_ptr));
    qe_assert(adjs);

    /* add to adjacency list */
    qe_hashtab_insert(g->adjacency_list, (qe_ptr)v, (qe_ptr)adjs);
    qe_debug("v:%p insert adjacency list:%p", v, adjs);

    return qe_ok;
}

static void remove_vertex(qe_graph_real *g, qe_const_ptr v)
{
    qe_ptr key, val;
    qe_array *adjs;
    qe_hashtab_iter iter;

    /* Remove other verties with this */
    qe_hashtab_iter_init(&iter, g->vertices);

    while (qe_hashtab_iter_next(&iter, &key, &val)) {
        
        if (!is_in_adjacency(g, val, v))
            continue;

        adjacency_remove(g, val, v);
        g->num_edges--;
    }

    qe_hashtab_remove(g->adjacency_list, (qe_ptr)v);
    qe_debug("v:%p remove adjacency list");

    qe_hashtab_remove(g->vertices, (qe_ptr)v);
    qe_debug("remove v:%p", v);
}

static void array_destroy_func(qe_ptr data)
{
    qe_debug("adjacency list:%p free", data);
    qe_free(data);
}

qe_graph *qe_graph_new_full(qe_val_str v_str_func, qe_destroy_notify v_destroy_func)
{
    qe_graph_real *g = qe_malloc(sizeof(qe_graph_real));
    qe_assert(g);
    qe_memset(g, 0, sizeof(qe_graph_real));

    g->vertices = qe_hashtab_new_full(qe_direct_hash, qe_direct_equal, QE_NULL, v_destroy_func);
    if (!g->vertices) {
        qe_free(g);
        qe_error("create hashtab for vertices failed");
        return QE_NULL;
    }

    g->adjacency_list = qe_hashtab_new_full(qe_direct_hash, qe_direct_equal, QE_NULL, array_destroy_func);

    g->v_str_func = v_str_func ? v_str_func : direct_str;

    qe_debug("create graph %p vertices:%p adjacency_list:%p",
        g, g->vertices, g->adjacency_list);

    return (qe_graph *)g;
}

qe_graph *qe_graph_new(void)
{
    return qe_graph_new_full(QE_NULL, QE_NULL);
}

qe_uint qe_graph_v(qe_graph *graph)
{
    if (!graph) {
        qe_error("graph null");
        return 0;
    }

    qe_graph_real *g = (qe_graph_real *)graph;

    if (!g->vertices) {
        qe_error("vertices null");
        return 0;
    }
    
    return qe_hashtab_size(g->vertices);
}

qe_uint qe_graph_e(qe_graph *graph)
{
    if (!graph) {
        qe_error("graph null");
        return 0;
    }

    qe_graph_real *g = (qe_graph_real *)graph;
    
    return g->num_edges;
}

qe_array *qe_graph_adj(qe_graph *graph, qe_const_ptr v)
{
    if (!graph || !v) {
        qe_error("invalid params");
        return 0;
    }

    qe_graph_real *g = (qe_graph_real *)graph;

    return get_adjacency(g, v);
}

qe_ret qe_graph_add_vertex(qe_graph *graph, qe_const_ptr v)
{
    if (!graph || !v) {
        qe_error("invalid params");
        return qe_err_param;
    }

    qe_graph_real *g = (qe_graph_real *)graph;

    if (find_vertex(g, v)) {
        qe_warning("v:%s already exist", g->v_str_func(v));
        return qe_ok;
    }

    return add_vertex(g, v);
}

void qe_graph_remove_vertex(qe_graph *graph, qe_const_ptr v)
{
    if (!graph || !v) {
        qe_error("invalid params");
        return;
    }

    qe_graph_real *g = (qe_graph_real *)graph;

    if (!find_vertex(g, v)) {
        qe_error("v:%s not found", g->v_str_func(v));
        return;
    }

    remove_vertex(g, v);
}

qe_ret qe_graph_add_edge(qe_graph *graph, qe_const_ptr v, qe_const_ptr w)
{
    int add = 0;

    if (!graph || !v || !w) {
        qe_error("invalid params");
        return qe_err_param;
    }

    qe_graph_real *g = (qe_graph_real *)graph;

    if (!find_vertex(g, v)) {
        add_vertex(g, v);
    }

    if (!find_vertex(g, w)) {
        add_vertex(g, w);
    }

    if (!is_in_adjacency(g, v, w)) {
        adjacency_add(g, v, w);
        add = 1;
    }

    if (!is_in_adjacency(g, w, v)) {
        adjacency_add(g, w, v);
        add = 1;
    }

    if (add) {
        g->num_edges++;
    }

    return qe_ok;
}

void qe_graph_remove_edge(qe_graph *graph, qe_const_ptr v, qe_const_ptr w)
{
    int remove = 0;

    if (!graph || !v || !w) {
        qe_error("invalid params");
        return;
    }

    qe_graph_real *g = (qe_graph_real *)graph;

    if (!find_vertex(g, v)) {
        qe_error("vertex %s not found", g->v_str_func(v));
        return;
    }

    if (!find_vertex(g, w)) {
        qe_error("vertex %s not found", g->v_str_func(w));
        return;
    }

    if (is_in_adjacency(g, v, w)) {
        adjacency_remove(g, v, w);
        remove = 1;
    }

    if (is_in_adjacency(g, w, v)) {
        adjacency_remove(g, w, v);
        remove = 1;
    }

    if (remove)
        g->num_edges--;
}

qe_uint qe_graph_degree(qe_graph *graph, qe_const_ptr v)
{
    if (!graph || !v) {
        qe_error("invalid params");
        return qe_err_param;
    }

    qe_graph_real *g = (qe_graph_real *)graph;

    qe_array *adjs = get_adjacency(g, v);
    if (!adjs) {
        return 0;
    }

    return adjs->len;
}

qe_uint qe_graph_max_degree(qe_graph *graph)
{
    int i;
    qe_ptr k, v;
    qe_uint max = 0;
    qe_array *adjs;
    qe_hashtab_iter iter;

    if (!graph) {
        qe_error("invalid params");
        return 0;
    }

    qe_graph_real *g = (qe_graph_real *)graph;

    qe_hashtab_iter_init(&iter, g->vertices);

    while (qe_hashtab_iter_next(&iter, &k, &v)) {
        adjs = get_adjacency(g, v);
        if (adjs->len > max) {
            max = adjs->len;
        }
    }

    return max;
}

void qe_graph_print(qe_graph *graph)
{
    int i;
    qe_uint md;
    qe_ptr k, v, n;
    qe_array *adjs;
    qe_hashtab_iter iter;

    if (!graph) {
        qe_error("invalid params");
        return;
    }

    qe_graph_real *g = (qe_graph_real *)graph;

    qe_printf("graph:%p v:%d e:%d md:%d"QE_ENDLINE,
        g, qe_hashtab_size(g->vertices), g->num_edges, qe_graph_max_degree(graph));

    qe_hashtab_iter_init(&iter, g->vertices);

    while (qe_hashtab_iter_next(&iter, &k, &v)) {
        adjs = get_adjacency(g, v);
        qe_printf("%s : ", g->v_str_func(v));
        for (i=0; i<adjs->len; i++) {
            n = qe_array_index(adjs, qe_ptr, i);
            qe_printf("%s ", g->v_str_func(n));
        }
        qe_printf(QE_ENDLINE);
    }
}

void qe_graph_destroy(qe_graph *graph)
{
    qe_ptr k, v;
    qe_array *adjs;
    qe_hashtab_iter iter;

    if (!graph)
        return;
    
    qe_graph_real *g = (qe_graph_real *)graph;

    /* free adjacency_list */
    qe_hashtab_destroy(g->adjacency_list);

    /* free vertices */
    qe_hashtab_destroy(g->vertices);

    qe_free(g);
}